1720C - Corners - CodeForces Solution

greedy implementation

Please click on ads to support us..

Python Code: 

t= int(input())

for i in range(t):
    n, m= [int(x) for x in input().split()]
    d= [list(map(int, input())) for x in range(n)]

    c= sum(sum(r) for r in d)
    perfect= False

    if (c == n*m):
        print(c-2)
    elif (c == 0):
        print(0)
    else:
        for p in range(n-1):
            for q in range(m-1):
                s= d[p][q] + d[p][q+1] + d[p+1][q] + d[p+1][q+1]
                if (s <= 2):
                    perfect= True
                    break
            if perfect: break

        print(c if perfect else c-1)

C++ Code: 

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair

const int N=2e5+5;
const int mod=1e9+7;
#include <vector>
#include <algorithm>
#include <iostream>
#include <cassert>
#include <map>
#include <set>
#include <cmath>
#include <array>






void solve(){

int n,m;
cin>>n>>m;

int cnt=0;
int a[n][m];

for(int i=0;i<n;i++){
    string s;
    cin>>s;
for(int j=0;j<m;j++){
    
    a[i][j]=s[j]-'0';
    cnt=cnt+a[i][j];
    
}

}

if(cnt==0)
{
    cout<<"0"<<endl;
    return;
    
}


int mini=INT_MAX;

for(int i=0;i<n-1;i++){
    for(int j=0;j<m-1;j++){
        int t=a[i][j]+a[i+1][j]+a[i][j+1]+a[i+1][j+1];
        
        if(t==0)continue;
        
        mini=min(t,mini);
    }
}

if(mini==1||mini==2){
    cout<<cnt<<endl;
}
else if(mini==3){
     cout<<cnt-1<<endl;
}
else{
     cout<<cnt-2<<endl;
}





}


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin>>T;
    
    
    while(T--){
        solve();
    }
   // solve();
}


Comments

Submit
0 Comments
More Questions

739. Daily Temperatures
647. Palindromic Substrings
583. Delete Operation for Two Strings
518. Coin Change 2
516. Longest Palindromic Subsequence
468. Validate IP Address
450. Delete Node in a BST
445. Add Two Numbers II
442. Find All Duplicates in an Array
437. Path Sum III
436. Find Right Interval
435. Non-overlapping Intervals
406. Queue Reconstruction by Height
380. Insert Delete GetRandom O(1)
332. Reconstruct Itinerary
368. Largest Divisible Subset
377. Combination Sum IV
322. Coin Change
307. Range Sum Query - Mutable
287. Find the Duplicate Number
279. Perfect Squares
275. H-Index II
274. H-Index
260. Single Number III
240. Search a 2D Matrix II
238. Product of Array Except Self
229. Majority Element II
222. Count Complete Tree Nodes
215. Kth Largest Element in an Array
198. House Robber